﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace UndirectedGraphs
{
    public class BreadthFirstPaths
    {
        private bool[] marked;     // marked[v] = is there an s-v path
        private int[] edgeTo;      // edgeTo[v] = previous edge on shortest s-v path
        private int[] distTo;      // distTo[v] = number of edges shortest s-v path
        private int INFINITY = int.MaxValue;

        /**
         * Computes the shortest path between the source vertex <tt>s</tt>
         * and every other vertex in the graph <tt>G</tt>.
         * @param G the graph
         * @param s the source vertex
         */

         public BreadthFirstPaths(Graph G, int s) {
            marked = new bool[G.V()];
            distTo = new int[G.V()];
            edgeTo = new int[G.V()];
            bfs(G, s);

            System.Diagnostics.Debug.Assert (check(G, s),  "true");
        }

         // breadth-first search from a single source
         private void bfs(Graph G, int s) {
            Queue<int> q = new Queue<int>();
            for (int v = 0; v < G.V(); v++) distTo[v] = INFINITY;

            distTo[s] = 0;
            marked[s] = true;
            q.Enqueue(s);

            while (q.Count() > 0) {
                int v = q.Dequeue();
                foreach (int w in G.adj(v))
                {
                    if (!marked[w])
                    {
                        edgeTo[w] = v;
                        distTo[w] = distTo[v] + 1;
                        marked[w] = true;
                        q.Enqueue(w);
                    }
                }
            }
    }

         /**
          * Is there a path between the source vertex <tt>s</tt> (or sources) and vertex <tt>v</tt>?
          * @param v the vertex
          * @return <tt>true</tt> if there is a path, and <tt>false</tt> otherwise
          */
         public bool hasPathTo(int v)
         {
             return marked[v];
         }

         /**
         * Returns the number of edges in a shortest path between the source vertex <tt>s</tt>
         * (or sources) and vertex <tt>v</tt>?
         * @param v the vertex
         * @return the number of edges in a shortest path
         */
         public int distanceTo(int v)
         {
             return distTo[v];
         }

         /**
          * Returns a shortest path between the source vertex <tt>s</tt> (or sources)
          * and <tt>v</tt>, or <tt>null</tt> if no such path.
          * @param v the vertex
          * @return the sequence of vertices on a shortest path, as an Iterable
          */
         public Stack<int> PathTo(int v)
         {
             if (!hasPathTo(v)) return null;
             Stack<int> path = new Stack<int>();
             int x;
             for (x = v; distTo[x] != 0; x = edgeTo[x])
                 path.Push(x);
             path.Push(x);
             return path;
         }



         private bool check(Graph G, int s) {

            // check that the distance of s = 0
            if (distTo[s] != 0) {
                Console.WriteLine("distance of source " + s + " to itself = " + distTo[s]);
                return false;
            }

            // check that for each edge v-w dist[w] <= dist[v] + 1
            // provided v is reachable from s
            for (int v = 0; v < G.V(); v++) {
                foreach (int w in G.adj(v)) {
                    if (hasPathTo(v) != hasPathTo(w)) {
                        Console.WriteLine("edge " + v + "-" + w);
                        Console.WriteLine("hasPathTo(" + v + ") = " + hasPathTo(v));
                        Console.WriteLine("hasPathTo(" + w + ") = " + hasPathTo(w));
                        return false;
                    }
                    if (hasPathTo(v) && (distTo[w] > distTo[v] + 1)) {
                        Console.WriteLine("edge " + v + "-" + w);
                        Console.WriteLine("distTo[" + v + "] = " + distTo[v]);
                        Console.WriteLine("distTo[" + w + "] = " + distTo[w]);
                        return false;
                    }
                }
            }

            // check that v = edgeTo[w] satisfies distTo[w] + distTo[v] + 1
            // provided v is reachable from s
            for (int w = 0; w < G.V(); w++) {
                if (!hasPathTo(w) || w == s) continue;
                int v = edgeTo[w];
                if (distTo[w] != distTo[v] + 1) {
                    Console.WriteLine(("shortest path edge " + v + "-" + w));
                    Console.WriteLine(("distTo[" + v + "] = " + distTo[v]));
                    Console.WriteLine(("distTo[" + w + "] = " + distTo[w]));
                    return false;
                }
            }

            return true;
        }
    }
}
